1. Field of the Invention
Embodiments of the invention relate generally to physics simulations and more specifically to hierarchical position-based dynamics.
2. Description of the Related Art
Conventional computer graphics (CG) engines are capable of generating highly realistic images representing real-world or imaginary scenes. These images are typically composed of a plurality of different particles. A collection of such particles can be used to represent different objects in the virtual graphics scene, including rocks, trees, cloth, water, and people, among others. Some CG engines perform physical simulations of the motion of the particles in the virtual graphics scene, thus simulating the motion of the objects represented by those particles. The physical simulations typically apply equations of motion to each particle to predict the position of the particle at a particular time step in the physical simulation. A wide variety of techniques are available for applying equations of motion to particles in the virtual graphics scene. One commonly-used technique is known as the “explicit Euler” technique.
In conventional systems, the explicit Euler technique can be used to predict the position of each particle in the virtual graphics scene by integrating a set of forces acting on the particle to generate one or more velocity components for the particle. The velocity components are then integrated to generate a position prediction for the particle. One problem with the explicit Euler technique is that each integral is approximated; thus, the position of the particle may not always be predicted with a high degree of accuracy, especially for larger time steps. Approximation errors can accumulate over multiple time steps, potentially causing the simulation to diverge, which may result in a numerical explosion.
One solution to the problems with the explicit Euler technique is to correct the generated position predictions based on a set of constraint equations associated with each particle. A constraint equation restricts the position of a particle and typically takes the form of an equality or of an inequality. For example, an equality constraint equation C1 that restricts the height HP, of a particle Pj to zero in a virtual graphics scene would be C1(Pj)=HPj=0. In another example, an inequality constraint equation C2 that restricts the distance between particles Pj and Pk to be less than a distance D would be C2(Pj,Pk)=|Pj−Pk|−D<0. The constraint equations for each particle can be solved to generate a position correction that, when applied to the position predictions generated by the explicit Euler technique, results in a corrected position prediction. Many techniques for solving constraint equations are known in the art.
For example, some physical simulations employ a Gauss-Seidel solver to solve the constraint equations for each particle. However, Gauss-Seidel solvers suffer from certain drawbacks. The main drawback is that each constraint is solved separately from all other constraints. This causes error corrections to propagate slowly through the particles and the solver to converge slowly to the correct solution. If the number of solver iterations is limited by a time budget, as is the case in computer games, the result computed by a Gauss-Seidel may diverge significantly from the true solution. In the case of a cloth simulation, this causes visual stretchiness.
There are methods that solve for all constraints simultaneously. Examples are the Conjugate Gradients method and the multi-grid method. For these methods to work, the constraints have to be linearized, which may be time consuming. In addition, the linearization can introduce stability problems because it replaces the true constraint functions by approximations which are only valid in a certain region.
As the foregoing illustrates, there remains a need in the art for a more effective way to simulate the motion of particles in a virtual graphics scene.